#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "../include/VFS_BST.h"

/*Creates the bst, returns the root b_node*/
b_node *bst_create()
{
	return NULL;
}

/*searches the BST on the basis of fullpath and returns the searched node. NULL -if not found*/
b_node *bst_search( b_node *bst_root, char *fullpath )
{
	b_node *cur_node;
	int cmp;
	cur_node=bst_root;
	while(cur_node!=NULL)
	{
		cmp=strcmp(fullpath,cur_node->full_path);
		//printf("Search:%s",cur_node->full_path);
		if(cmp==0)
			return cur_node;
		if(cmp<0)
		{
			cur_node=cur_node->left;
		}
		else
		{
			cur_node=cur_node->right;
		}
	}
	return NULL;
}


/* insert the bst node and returns root    0 on success , 1 on duplicate*/
int bst_insert ( b_node **bst_root_ptr, fd *data )
{
	b_node *cur_node,*new_node;
	char fullpath[MAX_PATH_SIZE+MAX_FILENAME_SIZE];
	int cmp;
	if(strcmp(data->path,"/")==0)
		strcat(strcpy(fullpath,data->path),data->file_name);
	else
	    strcat(strcat(strcpy(fullpath,data->path),"/"),data->file_name);
	if(*bst_root_ptr==NULL)
	{
		//printf("insert in root\n");
		new_node=(b_node *)malloc(sizeof(b_node));
		new_node->parent=NULL;
		new_node->left=NULL;
		new_node->right=NULL;
		strcpy(new_node->full_path,fullpath);
		new_node->file_desc=data;
		*bst_root_ptr=new_node;
		return 0;
	}
	else
	{
		cur_node=*bst_root_ptr;
		while(1)
		{
			cmp=strcmp(fullpath,cur_node->full_path);
			if(cmp==0)
			{
                return 1;
            }
			if(cmp<0)
			{
				if(cur_node->left==NULL)
				{
					new_node=(b_node *)malloc(sizeof(b_node));
					new_node->parent=cur_node;
					new_node->left=NULL;
					new_node->right=NULL;
					strcpy(new_node->full_path,fullpath);
					new_node->file_desc=data;
					cur_node->left=new_node;
					//printf("insert in left\n");
					return 0;
				}
				cur_node=cur_node->left;
			}
			else
			{
				if(cur_node->right==NULL)
				{
					new_node=(b_node *)malloc(sizeof(b_node));
					new_node->parent=cur_node;
					new_node->left=NULL;
					new_node->right=NULL;
					strcpy(new_node->full_path,fullpath);
					new_node->file_desc=data;
					cur_node->right=new_node;
					//printf("insert in right\n");
					return 0;
				}
				cur_node=cur_node->right;
			}
		}
	}
}

 
/* deletes the bst node and returns root . 0 on success and 1 if not found*/
int bst_delete(b_node **bst_root_ptr, char *fullpath)
{
	b_node *cur_node,*inorder_node;
	int cmp;
	int flag,inflag;
	cur_node=(*bst_root_ptr);
	flag=0;
	while(cur_node!=NULL)
	{
		cmp=strcmp(fullpath,cur_node->full_path);
		if(cmp==0)
		{
			if(cur_node->left==NULL && cur_node->right==NULL) //When both children are empty
			{
				if(flag==0)
				{
					free(cur_node);
					*bst_root_ptr=NULL;
					return 0;
				}
				if(flag==1)
				{
					cur_node->parent->left=NULL;
					free(cur_node);
					return 0;
				}
				else
				{
					cur_node->parent->right=NULL;
					free(cur_node);
					return 0;
				}
			}
			if(cur_node->left!=NULL && cur_node->right!=NULL) //When both children are present
			{
				//printf("2 c present\n");
                inorder_node=cur_node->left;//to get the inorder predicessor
				inflag=0;
				while(inorder_node->right!=NULL)
				{
					inflag=1;
					inorder_node=inorder_node->right;
				}
				if(inflag==0)// if inorder predecessor is the child itself
				{
					//printf("inor p c\n");
                    if(flag==0)
					{
						*bst_root_ptr=inorder_node;
						inorder_node->right=cur_node->right;
						inorder_node->parent=NULL;
						cur_node->right->parent=inorder_node;
						free(cur_node);
						return 0;
					}
					if(flag==1)
					{
						cur_node->parent->left=inorder_node;
						inorder_node->right=cur_node->right;
						inorder_node->parent=cur_node->parent;
						cur_node->right->parent=inorder_node;
						free(cur_node);
						return 0;
					}
					else
					{
						cur_node->parent->right=inorder_node;
						inorder_node->right=cur_node->right;
						inorder_node->parent=cur_node->parent;
						cur_node->right->parent=inorder_node;
						free(cur_node);
						return 0;
					}
				}
				else// if inorder predecessor is the grand child 
				{
					//printf("inor pre granc\n");
                    if(flag==0)
					{				
						*bst_root_ptr=inorder_node;
						inorder_node->parent->right=NULL;
						inorder_node->right=cur_node->right;
						inorder_node->left=cur_node->left;
						inorder_node->parent=NULL;
						cur_node->right->parent=inorder_node;
						cur_node->left->parent=inorder_node;
						free(cur_node);
						return 0;
					}
					if(flag==1)
					{
						cur_node->parent->left=inorder_node;
						inorder_node->parent->right=NULL;
						inorder_node->right=cur_node->right;
						inorder_node->left=cur_node->left;
						inorder_node->parent=cur_node->parent;
						cur_node->right->parent=inorder_node;
						cur_node->left->parent=inorder_node;
						free(cur_node);
						return 0;
					}
					else
					{
						cur_node->parent->right=inorder_node;
						inorder_node->parent->right=NULL;
						inorder_node->right=cur_node->right;
						inorder_node->left=cur_node->left;
						inorder_node->parent=cur_node->parent;
						cur_node->right->parent=inorder_node;
						cur_node->left->parent=inorder_node;
						free(cur_node);
						return 0;
					}
				}
			}
			if(cur_node->left!=NULL && cur_node->right==NULL) //When only left child
			{
                //printf("left");
				if(flag==0)
				{
					*bst_root_ptr=cur_node->left;
					cur_node->left->parent=NULL;
					free(cur_node);
					return 0;
				}
				if(flag==1)
				{
					cur_node->parent->left=cur_node->left;
					cur_node->left->parent=cur_node->parent;
					free(cur_node);
					return 0;
				}
				else
				{
					cur_node->parent->right=cur_node->left;
					cur_node->left->parent=cur_node->parent;
					free(cur_node);
					return 0;
				}
			}
			if(cur_node->left==NULL && cur_node->right!=NULL) //When only right child
			{
				//printf("right\n");
                if(flag==0)
				{
					*bst_root_ptr=cur_node->right;
					cur_node->right->parent=NULL;
					free(cur_node);
					return 0;
				}
				if(flag==1)
				{
					cur_node->parent->left=cur_node->right;
					cur_node->right->parent=cur_node->parent;
					free(cur_node);
					return 0;
				}
				else
				{
					cur_node->parent->right=cur_node->right;
					cur_node->right->parent=cur_node->parent;
					free(cur_node);
					return 0;
				}
			}

		}
		if(cmp<0)
		{
			flag=1;
			cur_node=cur_node->left;
		}
		else
		{
			flag=2;
			cur_node=cur_node->right;
		}
	}
	return 1;

}


/*Prints the bst*/
void print_inorder(b_node *bst_root)
{
	if(bst_root!=NULL)
	{
		print_inorder(bst_root->left);
		printf("%s\n",bst_root->full_path);
		print_inorder(bst_root->right);
	}
}
